package com.datastructure.test.thesuittimeofexchangestock;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class TheSuitableTimeOfExchangeStock {

    public static void main(String[] args) {
        TheSuitableTimeOfExchangeStock theSuitableTimeOfExchangeStock = new TheSuitableTimeOfExchangeStock();
        int[] data = {1,2,4,2,5,7,2,4,9,0};
        int i = theSuitableTimeOfExchangeStock.maxProfit(data);
        System.out.println(i);
    }

    public int maxProfit (int[] prices) {
        // write code here
        if (prices == null || prices.length < 2)
            return 0;
        int index = 0, length = prices.length;
        ArrayList<Interval> data = new ArrayList<>();
        while (index < length-1) {
            while (index<length-1&&prices[index]>prices[index+1]){
                index++;
            }
            int min = prices[index];
            while (index<length-1&&prices[index]<prices[index+1]){
                index++;
            }
            int max = prices[index];
            data.add(new Interval(min,max));
        }
        List<Interval> collect = merge(data);
         collect = collect.stream().sorted((interval, interval1) -> interval1.end - interval.end).limit(2).collect(Collectors.toList());
        if(collect.size()==1){
            return collect.get(0).end-collect.get(0).start;
        } else {
            return collect.get(0).end-collect.get(0).start+(collect.get(1).end-collect.get(1).start);
        }
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        intervals.sort(Comparator.comparingInt(v -> v.start));
        ArrayList<Interval> res = new ArrayList<>();
        int idx = -1;
        for(Interval interval : intervals){
            if(idx == -1 || interval.start > res.get(idx).end){ //若数组为空，或当前区间的起始位置小于结果list中最后区间的终止位置
                //不合并，直接将当前区间加入结果list
                res.add(interval);
                idx ++;
            }else{    //合并，选择较大的数作为最后区间的终止位置
                res.get(idx).end = Math.max(interval.end, res.get(idx).end);
            }
        }
        return res;
    }
}

class Interval {
     int start;
     int end;
     Interval() { start = 0; end = 0; }
     Interval(int s, int e) { start = s; end = e; }
 }
